題目說明

給定一個 set 數列，並給定一個 target，找到在這個 set 中能夠組合成 target 的所有數字組合，數字可以重複

解題思路

官大講解：

這是一題典型的 backtracking 與 dfs 題
掌握這兩個演算法的觀念就可以解答

不過 python code 在寫的時候有遇到 shallow copy 的問題，導致最後的結果都是 空陣列

今天比昨天厲害講解：

重點：
通常如果題目要求我們去求組合，我們幾乎都可以用 Backtracking 的方法來解

Backtracking 的基本模板：

• 因為會需要用的 Recursive 所以需要一個 Base case
• 去遍歷題目給的 input
• 把遍歷到的值加到暫時的 list
• call recursive helper
• 把暫時的 list 最後一個元素 pop 掉，為了要挪一個空位給下一個新的值

必要元素：

• input

• 暫時 list

• target

• 指針記下當時的位置跟值

• Time Complexity:

• Space Complexity:

程式碼

Approach 1: sum

class Solution:
    def __init__(self):
        self.res = []
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        comb = []
        self.dfs(candidates, target, 0, 0, comb)
        return self.res

    def dfs(self, candidates: List[int], target: int, idx: int, res_sum: int, comb: List[int]):
        if res_sum == target:
            curr_comb = [c for c in comb]
            self.res.append(curr_comb)
            return
        if res_sum > target:
            return
        for i in range(idx, len(candidates)):
            comb.append(candidates[i])
            self.dfs(candidates, target, i, res_sum + candidates[i], comb)
            comb.pop()

Approach 2: reminder

class Solution:
    def __init__(self):
        self.res = []
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        
        def backtracking_helper(nums, comb, reminder, idx):
            if reminder == 0:
                self.res.append(comb[:])
                return
            if reminder < 0:
                return
            for i in range(idx, len(nums)):
                comb.append(nums[i])
                backtracking_helper(nums, comb, reminder - nums[i], i)
                comb.pop()
        comb = []
        backtracking_helper(candidates, comb, target, 0)

        return self.res

其他討論

小技巧：python 的世界中要用 shallow copy 的方式，將值複製一份並 append 到 res
可以用 comb[:] 這個寫法

參考資料

1. Huifeng Guan(2020-02-04)。【每日一题】39. Combination Sum, 2/2/2020。摘自 Youtube (2023-01-24)
2. 今天比昨天厲害(2020-08-09)。leetcode 中文 | LeetCode 39. Combination Sum - Python思路總結。摘自 Youtube (2023-01-24)